package company.qianxing_F;

import java.util.Scanner;

public class Knapsack {

    public static void main(String[] args) {
        Knapsack s = new Knapsack();
        s.solve3();
    }

    private static int[] P;
    private static int[] V;
    private static int T;
    private int[][] dp;
    private int[] newResults = new int[T + 1];

    public void resolve4() {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt();
        int n = sc.nextInt();
        P = new int[n];
        V = new int[n];
        dp = new int[P.length + 1][T + 1];
        for (int i = 0; i < n; i++) {
            P[i] = sc.nextInt();
            V[i] = sc.nextInt();
        }
        int result = ksp(P.length, T);
        System.out.println(result);
    }

    public void solve3() {
        for (int i = 0; i < P.length; i++) {
            for (int j = 0; j <= T; j++) {
                for (int k = 0; k * V[i] <= j; k++) {
                    dp[i + 1][j] = Math.max(dp[i + 1][j], dp[i][j - k * V[i]] + k * P[i]);
                }
            }
        }
        System.out.println("最大价值为：" + dp[P.length][T]);
    }

    private int ksp(int i, int t) {
        // 开始填表
        for (int m = 0; m < i; m++) {
            for (int n = V[m]; n <= t; n++) {
                newResults[n] = Math.max(newResults[n], newResults[n - V[m]] + P[m]);
            }
        }
        return newResults[newResults.length - 1];
    }
}
